Skip to main content

第47章 贪心算法

贪心算法（Greedy Algorithm）是一种通过在每一步选择中采取局部最优策略，逐步构造完整解，期望最终得到全局最优解的算法思想。贪心只依据当前状态做最优决策，不考虑后续长远影响。

47.1 基本概念​

47.1.1 定义​

解决问题时，每一步只选取当前局面下最优的局部选择，不断更新问题状态，最终拼接出完整答案。 举例：硬币找零（人民币面额），每次选不超过剩余金额的最大硬币，硬币总数最少。

47.1.2 与其他算法区分​

  1. 分治：拆分独立子问题，递归求解后合并；贪心不拆分，持续做局部选择。
  2. 动态规划：存在重叠子问题，存储所有子问题最优解；贪心无存储，选择不可逆，依赖贪心性质。

47.2 两大核心必要性质​

贪心算法想要得到全局最优，必须同时满足两个条件：

  1. 贪心选择性质：全局最优解一定包含当前局部最优选择，每一步局部最优可逐步拼成全局最优。
  2. 最优子结构：原问题的最优解包含所有子问题的最优解（DP与贪心共有性质）。

47.3 通用实现步骤​

  1. 问题建模：把问题拆解成一系列分步选择；
  2. 设计贪心策略：定义“局部最优”标准（最小代价、最早结束、最小权等）；
  3. 循环执行局部选择，更新剩余约束条件；
  4. 校验最终解是否满足题目全部限制；
  5. 可行则输出，策略失效则更换算法（DP/分治）。

47.4 经典贪心例题​

47.4.1 硬币找零​

题意：给定硬币面额，用最少硬币凑指定金额。 贪心策略：每次选取≤剩余金额的最大面值硬币。

#include <vector>
#include <algorithm>
using namespace std;
// coins：降序排列的硬币面额，amount目标金额
int coinChange(vector<int>& coins, int amount) {
    int cnt = 0;
    for (int coin : coins) {
        while (amount >= coin) {
            amount -= coin;
            cnt++;
        }
        if (amount == 0) break;
    }
    return amount == 0 ? cnt : -1;
}

⚠️ 注意：该策略仅特定面额有效（人民币），如面额4凑6，贪心4+1+1（3枚），最优3+3（2枚），此时贪心失效。

47.4.2 活动选择问题​

题意：多个活动有起止时间，选出最多互不重叠的活动。 贪心策略：每次选结束时间最早的活动，留出更多剩余时间。

#include <vector>
#include <algorithm>
using namespace std;
struct Activity {
    int start;
    int end;
};
// 排序规则：按结束时间升序
bool cmp(Activity a, Activity b) {
    return a.end < b.end;
}
int selectActivities(vector<Activity>& acts) {
    sort(acts.begin(), acts.end(), cmp);
    int res = 1;
    int last = acts[0].end;
    for (int i = 1; i < acts.size(); i++) {
        if (acts[i].start >= last) {
            res++;
            last = acts[i].end;
        }
    }
    return res;
}

47.4.3 哈夫曼编码（数据压缩）​

题意：构造前缀编码，高频字符编码更短，压缩总长度最小。 贪心策略：每次选取频率最小的两个节点合并为新父节点，重复至只剩根。

#include <queue>
#include <vector>
using namespace std;
struct HuffmanNode {
    char ch;
    int freq;
    HuffmanNode *left, *right;
    HuffmanNode(char c, int f):ch(c),freq(f),left(nullptr),right(nullptr){}
    HuffmanNode(int f):ch(0),freq(f),left(nullptr),right(nullptr){}
};
// 最小堆比较规则
struct CmpNode {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};
HuffmanNode* buildHuffman(vector<char> chars, vector<int> freqs) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, CmpNode> heap;
    for (int i = 0; i < chars.size(); i++) {
        heap.push(new Huffman(chars[i], freqs[i]));
    }
    while (heap.size() > 1) {
        auto l = heap.top(); heap.pop();
        auto r = heap.top(); heap.pop();
        HuffmanNode* parent = new HuffmanNode(l->freq + r->freq);
        parent->left = l;
        parent->right = r;
        heap.push(parent);
    }
    return heap.top();
}

47.4.4 Kruskal最小生成树​

题意：无向带权连通图，选出总权最小无环生成树。 贪心策略：所有边按权升序，依次选取，并用并查集判环，选满n−1n-1条边停止。

#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
    int u, v, w;
};
// 并查集
struct UnionFind {
    vector<int> fa;
    UnionFind(int n) { fa.resize(n); for(int i=0;i<n;i++) fa[i]=i; }
    int find(int x) {
        if(fa[x]!=x) fa[x]=find(fa[x]);
        return fa[x];
    }
    bool unite(int x, int y) {
        x=find(x), y=find(y);
        if(x==y) return false;
        fa[y]=x; return true;
    }
};
int kruskal(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end(), [](Edge a, Edge b){
        return a.w < b.w;
    });
    UnionFind uf(n);
    int total = 0, cnt = 0;
    for(auto e : edges) {
        if(uf.unite(e.u, e.v)) {
            total += e.w;
            cnt++;
            if(cnt == n-1) break;
        }
    }
    return cnt == n ? total : -1;
}

47.5 复杂度分析​

  1. 排序开销：多数贪心需要排序，O(nlog⁡n)O(n\log n)；
  2. 遍历选择：单次遍历O(n)O(n)； 总时间复杂度主流贪心为O(nlog⁡n)O(n\log n)； 空间：存储输入数据、辅助结构（堆/并查集）O(n)O(n)。

47.6 适用条件与局限性​

47.6.1 适用场景​

同时满足贪心选择性质、最优子结构的问题：活动选择、最小生成树、Dijkstra最短路、哈夫曼编码。

47.6.2 缺点​

  1. 不满足贪心性质时，局部最优≠全局最优（01背包不能贪心，部分背包可以）；
  2. 策略依赖题目条件，微小修改会导致贪心失效；
  3. 很难严格数学证明正确性，直观推断容易出错。

47.7 区分：01背包 vs 部分背包​

  • 部分背包（物品可拆分）：贪心，优先拿单位价值最高；
  • 01背包（物品完整拿取）：贪心失效，必须动态规划。